﻿//礼物的最⼤价值（medium）: https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/
class Solution
{
public:
 int maxValue(vector<vector<int>>& grid) 
 {
 // 1. 创建 dp 表
 // 2. 初始化
 // 3. 填表
 // 4. 返回结果
 int m = grid.size(), n = grid[0].size();
 vector<vector<int>> dp(m + 1, vector<int>(n + 1));
 for(int i = 1; i <= m; i++)
 for(int j = 1; j <= n; j++)
 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 
1];
 return dp[m][n];
 }
};

//下降路径最⼩和（medium）: https://leetcode.cn/problems/minimum-falling-path-sum/
class Solution
{
public:
 int minFallingPathSum(vector<vector<int>>& matrix) 
 {
 // 1. 创建 dp 表
 // 2. 初始化
 // 3. 填表
 // 4. 返回结果
 int n = matrix.size();
 vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
 // 初始化第⼀⾏
 for(int j = 0; j < n + 2; j++) dp[0][j] = 0;
 for(int i = 1; i <= n; i++)
业课
 for(int j = 1; j <= n; j++)
 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 
+ 1])) + matrix[i - 1][j - 1];
 int ret = INT_MAX;
 for(int j = 1; j <= n; j++)
 ret = min(ret, dp[n][j]);
 
 return ret;
 }
};